upd(2020.10.5):修复一个手贱错误。
题意:一个 的网格图,每次连一条线,要求这条线:
- 至少包含两个点。
- 必须连续:也就是说,每一步可以继续向前画,也可以向左或向右转弯 。
- 不与以前画过的线重复。
构造一种包含 条线的画法,把整个图覆盖。
显然构造题。
一种容易想到的方法是:我们使前 条线每条经过两个点,最后一条线将剩余所有点连接。为了方便描述,我们以 的网格图为例,对其进行编号:

假设 ,则四条线段分别经过如下点:
基础思路有了,问题转化为如何根据点的编号求出其坐标。发现对于奇数行,编号正序;偶数行为倒序。我们根据这一特点对编号的行数进行分类,经过一定的数学推导,就可以得到行数和列数了。
pair<int, int> calcPos(int x) {
int div = (x - 1) / n + 1, pos = (x - 1) % n + 1;
if(div & 1) return make_pair(div, pos);
return make_pair(div, n-pos+1);
}
然后根据上面说过的思路,计算出所有线的情况,输出即可。
代码:
//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
int n, m, k;
pair<int, int> calcPos(int x) {
int div = (x - 1) / n + 1, pos = (x - 1) % n + 1;
if(div & 1) return make_pair(div, pos);
return make_pair(div, n-pos+1);
}
int main() {
scanf("%d%d%d", &m, &n, &k);
for(int i=1;i<k;i++) {
printf("2 ");
pair<int, int> _;
_ = calcPos((i<<1)-1);
printf("%d %d ", _.first, _.second);
_ = calcPos(i<<1);
printf("%d %d\n", _.first, _.second);
}
printf("%d ", n*m-((k-1)<<1));
for(int i=(k<<1)-1;i<=n*m;i++) {
pair<int, int> _;
_ = calcPos(i);
printf("%d %d ", _.first, _.second);
}
puts("");
return 0;
}